import static org.junit.Assert.*;

import java.util.ArrayList;

import org.junit.Test;


public class ABRNodeTest {

	protected ABRNode<Integer> createTree() {
		ABRNode<Integer> l2 = new ABRNode<Integer>(null, null, 1);
		ABRNode<Integer> r2 = new ABRNode<Integer>(null, null, 18);
		ABRNode<Integer> l1 = new ABRNode<Integer>(l2, r2, 17);
		ABRNode<Integer> r1 = new ABRNode<Integer>(null, null, 55);
		ABRNode<Integer> nd = new ABRNode<Integer>(l1, r1, 42);
		return nd;
	}
	
	protected ABRNode<Integer> createTree2() {
		ABRNode<Integer> l2 = new ABRNode<Integer>(null, null, 0);
		ABRNode<Integer> r2 = new ABRNode<Integer>(null, null, 18);
		ABRNode<Integer> l1 = new ABRNode<Integer>(l2, r2, 17);
		ABRNode<Integer> r1 = new ABRNode<Integer>(null, null, 55);
		ABRNode<Integer> nd = new ABRNode<Integer>(l1, r1, 42);
		return nd;
	}
	
	protected ABRNode<Integer> createTreeQ() {
		ABRNode<Integer> rrr = new ABRNode<Integer>(null, null, 12);
		ABRNode<Integer> ll = new ABRNode<Integer>(null, null, 2);
		ABRNode<Integer> l = new ABRNode<Integer>(ll, null, 3);
		ABRNode<Integer> lr = new ABRNode<Integer>(null, null, 5);
		ABRNode<Integer> rr = new ABRNode<Integer>(null, rrr, 8);
		ABRNode<Integer> r = new ABRNode<Integer>(lr, rr, 7);
		ABRNode<Integer> nd = new ABRNode<Integer>(l, r, 4);
		return nd;
	}
	
	@Test
	public void equalsTest() {
		ABRNode<Integer> nd = createTree();
		assertTrue("Equals itself", nd.equals(nd));
		assertTrue("Equals same", nd.equals(createTree()));
		assertTrue("Equals clone", nd.equals(nd.clone()));
		assertFalse("Different other", nd.equals(createTree2()));
	}
	
	@Test
	public void insertSmoke() {
		ABRNode<Integer> t = new ABRNode<Integer>(null, null, 10);
		t.insert(42);
		assertEquals("Simple insert right", new Integer(42), t.right.data);
		t.insert(3);
		assertEquals("Simple insert left", new Integer(3), t.left.data);
	}
	
	@Test
	public void insertQuestion() {
		ABRNode<Integer> t = createTreeQ();
		ABRNode<Integer> t2 = createTreeQ();
		t.insert(6);
		t2.getRight().getLeft().setRight(new ABRNode<Integer>(null, null, 6));
		assertEquals("Correct insetion", t2, t);
	}
	
	@Test
	public void searchTest() {
		ABRNode<Integer> t = createTree();
		assertTrue("Node found", t.find(1));
		assertTrue("Node found", t.find(18));
		assertTrue("Node found", t.find(42));
		assertTrue("Node found", t.find(55));
		assertTrue("Node found", t.find(17));
		assertFalse("Node not found", t.find(9898));
	}

	@Test
	public void searchTestQ() {
		ABRNode<Integer> t = createTreeQ();
		assertTrue("Node found", t.find(12));
		assertTrue("Node found", t.find(2));
		assertTrue("Node found", t.find(3));
		assertTrue("Node found", t.find(5));
		assertTrue("Node found", t.find(8));
		assertTrue("Node found", t.find(7));
		assertTrue("Node found", t.find(4));
		assertFalse("Node not found", t.find(9));
		assertFalse("Node not found", t.find(11));
	}
	
	@Test
	public void toStringTest() {
		ABRNode<Integer> t = createTreeQ();
		assertEquals("String conversion", "2,3,4,5,7,8,12", t.toString());
	}
	
	@Test
	public void toArrayListTest() {
		ABRNode<Integer> t = createTreeQ();
		ArrayList<Integer> al = new ArrayList<Integer>();
		al.add(2); al.add(3); al.add(4); al.add(5); al.add(7); al.add(8); al.add(12);
		assertEquals("ArrayList conversion", al, t.toArrayList());
	}
	
	@Test
	public void rangeTest1() {
		ABRNode<Integer> t = createTreeQ();
		ArrayList<Integer> al = new ArrayList<Integer>();
		al.add(2); al.add(3); al.add(4); al.add(5); al.add(7);
		assertEquals("ArrayList conversion", al, t.range(2, 7));
	}
	
	@Test
	public void rangeTest2() {
		ABRNode<Integer> t = createTreeQ();
		ArrayList<Integer> al = new ArrayList<Integer>();
		al.add(4); al.add(5); al.add(7);
		assertEquals("ArrayList conversion", al, t.range(4, 7));
	}
	
	@Test
	public void rangeTest3() {
		ABRNode<Integer> t = createTreeQ();
		ArrayList<Integer> al = new ArrayList<Integer>();
		al.add(7);
		assertEquals("ArrayList conversion", al, t.range(7, 7));
	}
	
	@Test
	public void rangeTest4() {
		ABRNode<Integer> t = createTreeQ();
		ArrayList<Integer> al = new ArrayList<Integer>();
		assertEquals("ArrayList conversion", al, t.range(13, 14));
	}
	
}
